#include <iostream>
#include <cstring>
#define ll long long
using namespace std;

const int N = 3e5 + 8;

ll totl;
int s[N], last[2], l, R, idx;
struct node
{
    int len, fail, cnt, son[26];
    void init(int _len)
    {
        len = _len, fail = cnt = 0;
        memset(son, 0, sizeof son);
    }
} t[N];
void init()
{
    last[0] = last[1] = totl = 0;
    idx = 2;
    l = 1e5 + 8, R = 1e5 + 7;
    memset(s, -1, sizeof s);
    t[0].init(0), t[1].init(-1);
    t[0].fail = 1;
}
int getfail(int p, int op)
{
    if (op)
        while (s[R - t[p].len - 1] != s[R])
            p = t[p].fail;
    else
        while (s[l + t[p].len + 1] != s[l])
            p = t[p].fail;
    return p;
}
void insert(int x, int op)
{
    (!op ? s[--l] : s[++R]) = x;
    int father = getfail(last[op], op);
    int now = t[father].son[x];

    if (!now) {
        now = idx++;
        t[now].init(t[father].len + 2);
        t[now].fail = t[getfail(t[father].fail, op)].son[x];
        t[now].cnt = t[t[now].fail].cnt + 1;
        t[father].son[x] = now;
    }
    last[op] = now;
    if (R - l + 1 == t[now].len)
        last[op ^ 1] = now;
    totl += t[now].cnt;
}
int main()
{
    int op, n;
    char x;
    while (scanf("%d", &n) != EOF) {
        init();
        while (n--) {
            scanf("%d", &op);
            if (op == 1 || op == 2) {
                scanf(" %c", &x);
                insert(x - 'a', op == 1);
            } else if (op == 3)
                printf("%d\n", idx - 2);
            else
                printf("%lld\n", totl);
        }
    }
    return 0;
}